//给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。 
//
// 计算置位位数 就是二进制表示中 1 的个数。 
//
// 
// 例如， 21 的二进制表示 10101 有 3 个计算置位。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：left = 6, right = 10
//输出：4
//解释：
//6 -> 110 (2 个计算置位，2 是质数)
//7 -> 111 (3 个计算置位，3 是质数)
//9 -> 1001 (2 个计算置位，2 是质数)
//10-> 1010 (2 个计算置位，2 是质数)
//共计 4 个计算置位为质数的数字。
// 
//
// 示例 2： 
//
// 
//输入：left = 10, right = 15
//输出：5
//解释：
//10 -> 1010 (2 个计算置位, 2 是质数)
//11 -> 1011 (3 个计算置位, 3 是质数)
//12 -> 1100 (2 个计算置位, 2 是质数)
//13 -> 1101 (3 个计算置位, 3 是质数)
//14 -> 1110 (3 个计算置位, 3 是质数)
//15 -> 1111 (4 个计算置位, 4 不是质数)
//共计 5 个计算置位为质数的数字。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= left <= right <= 106 
// 0 <= right - left <= 104 
// 
// Related Topics 位运算 数学 
// 👍 117 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

public class PrimeNumberOfSetBitsInBinaryRepresentation {
    public static void main(String[] args) {
        new PrimeNumberOfSetBitsInBinaryRepresentation().new Solution().countPrimeSetBits(6, 10);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 最多32个1
        private Set<Integer> set = new HashSet<Integer>(){{
            add(2);add(3);add(5);add(7);add(11);add(13);add(17);add(19);
            add(23);add(29);add(31);
        }};
        public int countPrimeSetBits(int left, int right) {
            int res = 0;
            int count, num;
            for (int i = left; i <= right ; i++) {
                // 直接使用Integer.bitCount(i)也是一样的
                count = 0;
                num = i;
                while (num != 0){
                    count++;
                    num &= (num - 1);
                }
                if (set.contains(count)) res++;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}